#include<iostream>
#include<string>
using namespace std;

int ans[20];  // 存储结果
char pp[5] = {'e', 'd', 'g', 'n', 'b'};  // 模式字符串
int next1[2000050];  // KMP算法中的next数组
// 构建next数组
void print(int n)
{
    cout<<endl;
    for(int i=0;i<n;i++){
        cout<<next1[i]<<" ";
    }
    cout<<endl;
}
    void buildNext(string pp) {
    next1[0]=-1;
    for(int i=1;i<pp.length();i++){
        int zb=next1[i];
        while(zb>=0){
            if(pp[zb]==pp[i])break;
            zb=next1[zb];
        }
        next1[i+1]=zb+1;
    }
    //print(pp.length());
}
string sp="edgnb";
int main() {
    int n;
    cin >> n;  // 输入n个测试案例
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;  // 输入要匹配的字符串
        int k;
        cin >> k;  // 模式的重复次数
        next1[0]=-1;
        string pp="";
        for(int j=1;j<=k;j++){
            pp+=sp;
        }
            buildNext(pp);
            int zb1 = 0, zb2 = 0;  // zb1是文本指针，zb2是模式指针
        while (zb1 < s.length()) {
            if (s[zb1] == pp[zb2]) {  // 如果字符匹配
                zb1++;
                zb2++;
            } else {
                zb2 = next1[zb2];  // 回溯模式指针
                if (zb2 == -1) {
                    zb1++;
                    zb2 = 0;
                }
            }
            // 如果成功匹配了整个模式
            if (zb2 == 5 * k) {
                ans[i]++;  // 计数匹配成功的次数
                zb2 = next1[zb2];  // 回溯模式指针，准备寻找下一个匹配
            }
        }
        // for(int j=0;j<k*5;j++)cout<<next1[j]<<" ";
        // cout<<endl;
    }
    // 输出每个测试案例的结果
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}
//next匹配串构建
//0位赋为-1
//(1)第一位赋0；
//(2)next1比较，匹配成功到赋值下一位。
//kmp:（1）双变量；
//（2）匹配失败，next1，直到-1，带匹配串++。模式串归0
//成功，若继续，则pp=next【pp】